/**
 * Copyright (c) 2021-2023 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

{% for arg, fwdArg, prec in [('', '', '(%s < %s)'), (', mustPrecede: (lhs: ' + T + ', rhs: ' + T + ') => boolean', ', mustPrecede', 'mustPrecede(%s, %s)')] %}
{%- if T == 'Object' and arg == '' %}
{%- continue %}
{%- elif T == 'boolean' and arg == '' %}
{%- set prec = '((%s) ? 1 : 0) < ((%s) ? 1 : 0)' %}
{%- endif %}
function bubbleSort(arr: {{T}}[], startIndex: int, endIndex: int{{arg}}): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if ({{prec % ('arr[i + 1]', 'arr[i]')}}) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: {{T}}[], startIndex: int, endIndex: int{{arg}}): void {
    if (startIndex != 0) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while ({{prec % ('tmp', 'arr[pos - 1]')}}) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if ({{prec % ('tmp', 'arr[startIndex]')}}) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while ({{prec % ('tmp', 'arr[pos - 1]')}}) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}

{%- if T != "boolean" %}
function heapSortUp(arr: {{T}}[], idxFromStart: int, startIndex: int, heapRoot: int{{arg}}): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!{{prec % ('arr[startIndex + p]', 'tmp')}}) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: {{T}}[], idxFromStart: int, startIndex: int, endIndex: int{{arg}}): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if ({{prec % ('arr[childIndex]', 'arr[childIndex + 1]')}}) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot{{fwdArg}})
}

export function heapSort(arr: {{T}}[], startIndex: int, endIndex: int{{arg}}): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex{{fwdArg}})
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i{{fwdArg}})
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: {{T}}[], index1: int, index2: int, index3: int{{arg}}): void {
    let swap_idx = index2
    if ({{prec % ('arr[index1]', 'arr[index2]')}}) {
        if ({{prec % ('arr[index3]', 'arr[index1]')}}) {
            return
        }
        if ({{prec % ('arr[index3]', 'arr[index2]')}}) {
            swap_idx = index3
        }
    } else {
        if (!{{prec % ('arr[index3]', 'arr[index1]')}}) {
            return
        }
        if ({{prec % ('arr[index2]', 'arr[index3]')}}) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: {{T}}[], startIndex: int, endIndex: int{{arg}}): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ({{prec % ('arr[i]', 'pivot')}}) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !{{prec % ('arr[j]', 'pivot')}}) {
            j--
        }
    } else {
        while (!{{prec % ('arr[j]', 'pivot')}}) {
            j--
        }
    }
    while (i < j) {
        // Here !{{prec % ('arr[i]', 'pivot')}} and {{prec % ('arr[j]', 'pivot')}} holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while ({{prec % ('arr[++i]', 'pivot')}}) {}
        while (!{{prec % ('arr[--j]', 'pivot')}}) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: {{T}}[], startIndex: int, endIndex: int{{arg}}): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ({{prec % ('pivot', 'arr[j]')}}) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !{{prec % ('pivot', 'arr[i]')}}) {
            i++
        }
    } else {
        while (!{{prec % ('pivot', 'arr[i]')}}) {
            i++
        }
    }
    while (i < j) {
        // Here {{prec % ('pivot', 'arr[i]')}} and !{{prec % ('pivot', 'arr[j]')}} holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!{{prec % ('pivot', 'arr[++i]')}}) {}
        while ({{prec % ('pivot', 'arr[--j]')}}) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

{% for quickUpTo in [3, 40] %}
function quickSortImpl{{quickUpTo}}(arr: {{T}}[], startIndex: int, endIndex: int, maxDepth: int{{arg}}): void {
    while (endIndex - startIndex > {{quickUpTo}}) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex{{fwdArg}})
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2{{fwdArg}})
        {%- if arg == '' %}
        if (startIndex > 0 && !{{prec % ('arr[startIndex - 1]', 'arr[startIndex]')}}) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array 
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex{{fwdArg}}) + 1
            continue
        }
        {%- endif %}
        let p = quickSortSplit(arr, startIndex, endIndex{{fwdArg}})
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl{{quickUpTo}}(arr, startIndex, p, maxDepth{{fwdArg}})
            startIndex = p + 1
        } else {
            quickSortImpl{{quickUpTo}}(arr, p + 1, endIndex, maxDepth{{fwdArg}})
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex{{fwdArg}})
}
{%- endfor %}

function quickSort(arr: {{T}}[], startIndex: int, endIndex: int{{arg}}): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3{{fwdArg}})
}
{%- endif %}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: {{T}}[], startIndex: int, endIndex: int{{arg}}): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    {% if T == "boolean" -%}
        {%- if arg == '' %}
    countSortBools(arr, startIndex, endIndex)
        {%- else %}
    if ({{prec % ('false', 'true')}}) {
        countSortBools(arr, startIndex, endIndex)
    } else {
        countSortBoolsInv(arr, startIndex, endIndex)
    }
        {%- endif %}
    {%- else %}
    {% if T == "byte" and arg == '' %}
    if (endIndex - startIndex > 1024) {
        countSort(arr, startIndex, endIndex)
    }
    {%- endif %}
    quickSort(arr, startIndex, endIndex{{fwdArg}});
    {%- endif %}
}

{% endfor %}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort(arr: {{T}}[], mustPrecede: (lhs: {{T}}, rhs: {{T}}) => boolean): void {
    sort(arr, 0, arr.length, mustPrecede);
}

export function sort(arr: {{T}}[], startIndex: int, mustPrecede: (lhs: {{T}}, rhs: {{T}}) => boolean): void {
    sort(arr, startIndex, arr.length, mustPrecede)
}

{% if T != "Object" -%}

{%- if T == 'byte' %}
function countSort(arr: byte[], startIndex: int, endIndex: int): void {
    const cnts = new int[256]
    for (let i = startIndex; i < endIndex; i++) {
        cnts[arr[i] + 128]++
    }
    let idx = 0
    for (let i = 0; i < 256; i++) {
        for (let j = 0; j < cnts[i]; j++) {
            arr[startIndex + idx++] = (i - 128) as byte
        }
    }
}
{%- elif T == 'boolean' %}
function countSortTruthCnt(arr: boolean[], startIndex: int, endIndex: int): int {
    let truthCnt = 0
    for (let i = startIndex; i < endIndex; i++) {
        if (arr[i]) {
            truthCnt++
        }
    }
    return truthCnt
}

function countSortBools(arr: boolean[], startIndex: int, endIndex: int): void {
    const truthCnt = countSortTruthCnt(arr, startIndex, endIndex)
    for (let i = startIndex; i < endIndex - truthCnt; i++) {
            arr[i] = false
        }
    for (let i = 0; i < truthCnt; i++) {
        arr[endIndex - truthCnt + i] = true
    }
}
function countSortBoolsInv(arr: boolean[], startIndex: int, endIndex: int): void {
    const truthCnt = countSortTruthCnt(arr, startIndex, endIndex)
    for (let i = 0; i < truthCnt; i++) {
        arr[startIndex + i] = true
    }
    for (let i = startIndex + truthCnt; i < endIndex; i++) {
        arr[i] = false
    }
}
{%- endif %}

export function sort(arr: {{T}}[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

export function sort(arr: {{T}}[]): void {
    sort(arr, 0, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortData{{T}} {
    name: string
    arr: {{T}}[]

    constructor(name: string, arr: {{T}}[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: {{T}}[]): {{T}}[] {
    let c = new {{T}}[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd(l: {{T}}, r: {{T}}): boolean {
{%- set mapMPArg = '%s' if T != 'boolean' else '((%s) ? 1 : 0)' %}
    return {{mapMPArg % 'l'}} < {{mapMPArg % 'r'}}
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv(l: {{T}}, r: {{T}}): boolean {
    return {{mapMPArg % 'r'}} < {{mapMPArg % 'l'}}
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: {{T}}[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: {{T}}[]) {
    {%- for arg in ['', ', test_sortAllOnCmpFwd', ', test_sortAllOnCmpInv'] %}
    // block for comparator `{{arg[3:]}}`
    if (true) {
        const sorts: test_SortData{{T}}[] = new test_SortData{{T}}[10]
        let lastSort = 0
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length{{arg}})
        sorts[lastSort++] = new test_SortData{{T}}("bubble", bubbled)

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length{{arg}})
        sorts[lastSort++] = new test_SortData{{T}}("insertion", insertion)

        {%- if T == 'byte' and arg == '' %}
        const cnt = test_sortCopy(arr)
        countSort(cnt, 0, cnt.length)
        sorts[lastSort++] = new test_SortData{{T}}("cnt()", cnt)
        {%- endif %}

        {% if T == 'boolean' %}
        const bcnt = test_sortCopy(arr)
            {%- if arg != ', test_sortAllOnCmpInv' %}
        countSortBools(bcnt, 0, bcnt.length)
            {%- else %}
        countSortBoolsInv(bcnt, 0, bcnt.length)
            {%- endif %}
        sorts[lastSort++] = new test_SortData{{T}}("bools cnt()", bcnt)
        {%- else %}
        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length{{arg}})
        sorts[lastSort++] = new test_SortData{{T}}("heap", heaped)

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length{{arg}})
        sorts[lastSort++] = new test_SortData{{T}}("quick", quicked)

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length{{arg}})
        sorts[lastSort++] = new test_SortData{{T}}("quick with insertion", quickedInsertion)
        {%- endif %}

        const just = test_sortCopy(arr)
        sort(just{{arg}})
        sorts[lastSort++] = new test_SortData{{T}}("sort()", just)

        for (let s = 1; s < lastSort; s++) {
            for (let i = 0; i < arr.length; i++) {
                if (sorts[0].arr[i] != sorts[s].arr[i]) {
                    console.println(sorts[0].name + ': ')
                    test_printArr(sorts[0].arr, 0, arr.length)
                    console.println(sorts[s].name + ': ')
                    test_printArr(sorts[s].arr, 0, arr.length)
                    throw new Error("sorts {{arg[3:]}} are not equal: " + sorts[0].name + ' ' + sorts[s].name + ' for {{T}}')
                }
            }
        }
    }
    {%- endfor %}
}
// ======== end of tests section ========
{% endif %}
